package leetcode.templates.trees.segment;


public class StNode {

	private int LeftRange, Mid, RightRange;
	private StNode leftChild, rightChild;
	private Integer value;

	public StNode(int left, int right) {
		this.LeftRange = left;
		this.RightRange = right;
		this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
		this.value = 0;
	}

	private StNode leftNode() {
		if (this.leftChild == null) {
			this.leftChild = new StNode(this.LeftRange, this.Mid);
		}
		return this.leftChild;
	}

	private StNode rightNode() {
		if (this.rightChild == null) {
			this.rightChild = new StNode(this.Mid + 1, this.RightRange);
		}
		return this.rightChild;
	}

	private void addValue(int value) {
		this.value = this.value == null ? value : this.value + value;
	}

	public void add(int left, int right, int add) {
		if (left > right) {
			return;
		}
		if (left == this.LeftRange && right == this.RightRange) {
			this.addValue(add);
		} else {
			pushdown();
			this.leftNode().add(left, Math.min(this.Mid, right), add);
			this.rightNode().add(Math.max(this.Mid + 1, left), right, add);
		}
	}

	public int query(int index) {
		if (this.LeftRange == index && index == this.RightRange) {
			return value;
		}
		pushdown();
		if (index <= this.Mid) {
			return this.leftNode().query(index);
		}
		return this.rightNode().query(index);
	}

	private void pushdown() {
		if (this.value != null) {
			this.leftNode().addValue(this.value);
			this.rightNode().addValue(this.value);
			this.value = null;
		}
	}

}
